class Solution {
    public:
        int lastStoneWeightII(vector<int>& stones) {
            int n = stones.size(),sum = 0;
            for(auto& x: stones)    sum+=x;
            int target = sum/2;
            vector<vector<int>> dp(n+1,vector<int>(target+1));
            for(int i = 0; i < target+1 ; i++)   dp[0][i] = 0;
            for(int i = 0; i < n+1 ; i++)   dp[i][0] = 1;
    
            int maxr=0;
            for(int i = 1 ; i< n+1; i++){
                for(int j = 1 ; j < target+1 ;j++){
                    dp[i][j] = j>=stones[i-1] ? dp[i-1][j-stones[i-1]] ||dp[i-1][j] :dp[i-1][j];
                    if(dp[i][j] && i == n){
                        maxr = max(maxr,j);
                    }
                }
            }
            return abs(sum-2*maxr);
        } 
    };